剑指Offer34 丑数

题目描述

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路

第一反应肯定是暴力法呗；但是我们低估了丑数也不是那么多的；毕竟丑数相当于(2^x)(3^y)(5^z);所以数量级是非常大的；

数组储存，这种方法书上说了半天也没看懂，还不如自己来呢；其实呢就相当于数组里已经存好了数，现在要加一个，这个数从哪里来的，其实就看当前，2为首，3为首，5为首他们的最新值谁最小；
举个例子啊
(2,3,4,5,6,8,9,10)
4是怎么来的，之前的数组已经有2，3了，然后我们对于2，3，5，都给2乘一下；找到最小值；这时肯定知道不能是3对吧；那么2*2=4；此时这个2在乘以2的次数就消耗掉了；比如6来说，此时对于这个2，就只能乘以3，或者5得到最小值；这样我们最后也是可以得到数组的；

代码

static public int GetUgly1(int index)
   {
       if (index<=0)
           return 0;
       int a[]=new int[index];
       a[0]=1;
       int pow2=0,pow3=0,pow5=0;
       for (int i = 1; i < index; i++) {
           a[i]=Math.min(5*a[pow5],Math.min(2*a[pow2],3*a[pow3]));
           if (a[i]==2*a[pow2])
               pow2++;
           if (a[i]==3*a[pow3])
               pow3++;
           if (a[i]==5*a[pow5])
               pow5++;
       }
       return a[index-1];
   }

收获

加油，努力；

2017-03-31